# 假设你设计一个游戏，用一个 m 行 n 列的 2D 网格来存储你的游戏地图。
#
#  起始的时候，每个格子的地形都被默认标记为「水」。我们可以通过使用 addLand 进行操作，将位置 (row, col) 的「水」变成「陆地」。
#
#  你将会被给定一个列表，来记录所有需要被操作的位置，然后你需要返回计算出来 每次 addLand 操作后岛屿的数量。
#
#  注意：一个岛的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。
#
#  请仔细阅读下方示例与解析，更加深入了解岛屿的判定。
#
#  示例:
#
#  输入: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
# 输出: [1,1,2,3]
#
#
#  解析:
#
#  起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」）
#
#  0 0 0
# 0 0 0
# 0 0 0
#
#
#  操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。
#
#  1 0 0
# 0 0 0   Number of islands = 1
# 0 0 0
#
#
#  操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。
#
#  1 1 0
# 0 0 0   岛屿的数量为 1
# 0 0 0
#
#
#  操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。
#
#  1 1 0
# 0 0 1   岛屿的数量为 2
# 0 0 0
#
#
#  操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。
#
#  1 1 0
# 0 0 1   岛屿的数量为 3
# 0 1 0
#
#
#  拓展：
#
#  你是否能在 O(k log mn) 的时间复杂度程度内完成每次的计算？（k 表示 positions 的长度）
#  Related Topics 并查集
#  👍 41 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    """
    每次加入一个 岛屿，检查周围的岛屿是否已经联通，联通的话则 记录到已经联通的岛屿，否则岛屿数量加一
    注意可能出现加入岛屿后， 多个岛屿合并成一个岛屿，那么要把之前的岛屿合并成一个岛屿
    """
    count = 0

    parent = []

    def setParent(self, key):
        self.parent[key] = key
        self.count += 1

    def restore(self, m, n):
        self.parent = [-1 for _ in range(0, m) for _ in range(0, n)]
        print(self.parent)

    # 查找代表
    def find(self, i):
        if self.parent[i] != i:
            return self.find(self.parent[i])

        return self.parent[i]

    # 并查更新
    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)

        # 两个节点必须不同
        if rootx != rooty:
            if rootx > rooty:
                self.parent[rooty] = rootx
            elif rooty > rootx:
                self.parent[rootx] = rooty

            self.count -= 1

    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:

        self.restore(m, n)

        res = []

        overlap = set()

        for point in positions:
            overlap.clear()
            r = point[0]
            c = point[1]

            # 岛屿的坐标
            key = r * n + c

            if self.parent[key]!=-1:
                res.append(self.count)
                continue

            # 如果相连的节点是岛屿，那么把当前岛屿坐标加入到待处理的岛屿列表
            # top ,bottom ,left ,right
            if r > 0 and self.parent[(r - 1) * n + c] != -1:
                overlap.add((r - 1) * n + c)

            if r < m - 1 and self.parent[(r + 1) * n + c] != -1:
                overlap.add((r + 1) * n + c)

            if c > 0 and self.parent[r * n + c - 1] != -1:
                overlap.add(r * n + c - 1)

            if c < n - 1 and self.parent[r * n + c + 1] != -1:
                overlap.add(r * n + c + 1)

            self.setParent(key)

            for i in overlap:
                self.union(i, key)

            res.append(self.count)

        return res

    # leetcode submit region end(Prohibit modification and deletion)


print(Solution().numIslands2(m=3, n=3, positions=[[0,0],[0,1],[1,2],[1,2]]))
